package com.qf.pojo.day01;

/**
 *
 * 19. 如何找到单向链表的中间元素
 *     设定两个指针slow、fast
 *     从头指针开始，每次fast指针前进2步, slow指针前进1步
 *     当fast指针走到链表结尾位置, slow指针所处位置的元素就是中间元素.
 *
 *
 * @author lixu
 */
public class isMiddleDemo {


    //单向链表
    private static class Node<T>{
        T value;
        Node<T> next;//后继

        public Node(T value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        //算法： 解决问题的方法或步骤

        Node node1 = new Node(5);
        Node node2 = new Node(8);
        Node node3 = new Node(2);
        Node node4 = new Node(1);
        Node node5 = new Node(9);
        Node node6 = new Node(7);

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;


        System.out.println(isMiddle(node1).value);




    }

    /**
     * 算法： 求链表的中间节点   O(n+3) ~ O(n)
     * @param node1
     * @return
     */
    private static Node isMiddle(Node node1) {//链表头节点  --》 规模是n长度
        //快
        Node fastNode = node1;//1
        //慢
        Node slowNode = node1;//1
        //快 前进2个
        //慢 前进1个
        //fastNode!= null 节点为偶数时
        //fastNode.next!=null 节点为奇数时

        while (fastNode!= null && fastNode.next!=null){//1    n/2次*2=n
            //往下走 2步
            fastNode = fastNode.next.next;//1
            //1步
            slowNode = slowNode.next;//1
        }
        //中间元素
        return slowNode;
    }


}
